In recent years, a software defined network (SDN) related technology represented by OpenFlow has been drawing attention in a network field. In OpenFlow, a packet-format data forwarding function and a control function such as switching and routing, which are included in conventional network devices such as a switch and a router, are separately provided to a switch (OpenFlow switch) and a controller (OpenFlow controller).
The OpenFlow controller controls data forwarding performed by the OpenFlow switch in accordance with the OpenFlow protocol. In other words, in OpenFlow, the controller controls a plurality of switches existing in a network in a centralized manner. Unlike conventional network control, in OpenFlow, in order to allow communications between two communication nodes, the controller needs to determine an optimal path and set (distribute) the flow table for (to) the switches existing on the path. Note that, in the same manner as in the conventional network control, the controller can calculate the shortest path based on a Dijkstra's algorithm (Single Source Shortest Path Algorithm).
Further, recent development of cloud computing allows a user to boot virtual machines (VMs) as an infrastructure, as many as necessary when needed. For example, Amazon (trademark) and Google (trademark) provide Infrastructure as a Service (IaaS) being a service that lends a machine resource such as a server environment in units of VMs.
The following are related arts to the invention.    [Patent document 1] Japanese Patent Laid-Open Publication No. JP 2005-94222    [Non-patent document 1] E. W. Dijkstra, “A Note on Two Problems in Connextion with Graphs”, Numerische Mathematik, Vol. 1, pp. 269-271, 1959    [Non-patent document 2] George T. Heineman et al, “Algorithm Quick References”, pp. 169-177, O'Reilly, April 2010